package com.dhu.graph.basic.paths.impls;

import com.dhu.graph.basic.GraphImpls.Graph;
import com.dhu.graph.basic.paths.Paths;
import com.dhu.graph.utils.LinkStack;

import java.util.Stack;

/**
 * @Description:
 * 深度优先查找DFS,Path对象聚合Graph对象
 * @author: snow
 * @Date: 2020-04-10
 **/
public class DepthFirstPaths implements Paths {
    private boolean [] marked;  //定点是否已经被访问过
    private Integer [] edgeTo;  //edge[i]表示从起点到定点i路径上的i之前一个定点
    private final Integer s;

    public DepthFirstPaths(Graph G, int s) {
        this.s = s;
        marked = new boolean[G.getVertexes()];
        edgeTo = new Integer[G.getVertexes()];
        dfs(G,s);
    }

    /**
     * 深度优先搜索的核心方法，递归查找
     * @param G
     * @param v
     */
    private void dfs(Graph G, int v){
        marked[v] = true;
        for (int w : G.adj(v)){
            if(!marked[w]){
                edgeTo[w] = v;
                dfs(G,w);
            }
        }
    }
    private void dfs2(Graph G, int s){
        Stack<Integer> stack = new Stack<>();
        marked[s] = true;
        stack.push(s);
        while(!stack.isEmpty()){
            Integer pop = stack.pop();
            for (Integer w : G.adj(pop)) {
                if(!marked(w)){
                    edgeTo[w] = pop;
                    marked[w] = true;
                    stack.push(w);
                }
            }
        }
    }

    private boolean marked(int v){
        return marked[v];
    }

    @Override
    public Iterable<Integer> pathsTo(int v) {
        if(!hasPathTo(v)) return null;
        LinkStack<Integer> stack = new LinkStack<>();
        for(int x = v; x != s; x = edgeTo[x]){
            stack.push(edgeTo[x]);
        }
        stack.push(v);
        return stack;
    }

    @Override
    public boolean hasPathTo(Integer v) {
        return marked[v];
    }

}
